Section: New Results

Estimation of Parallel Complexity with Rewriting Techniques

Participants : Christophe Alias, Laure Gonnord, Carsten Fuhs [(Birbeck, UK)] .

We show how monotone interpretations - a termination analysis technique for term rewriting systems - can be used to assess the inherent parallelism of recursive programs manipulating inductive data structures. As a side effect, we show how monotone interpretations specify a parallel execution order, and how our approach extends naturally affine scheduling - a powerful analysis used in parallelising compilers - to recursive programs. This preliminary work opens new perspectives in automatic parallelisation.

This work has been published in the Workshop on Termination, [15].